---
title: "CLH和MCS算法"
categories:
- java
- concurrent
tags:
---

<div id="content">
<div id="table-of-contents">
<h2>Table of Contents</h2>
<div id="text-table-of-contents">
<ul>
<li><a href="#orgc8d2e1f">CLH algorithm</a></li>
<li><a href="#org551edee">MCS algorithm</a></li>
<li><a href="#org1515987">SMP(Symmetric Multi-Processor)</a></li>
<li><a href="#orga5d66e8">NUMA(Non-Uniform Memory Access)</a></li>
</ul>
</div>
</div>
<div class="outline-2" id="outline-container-orgc8d2e1f">
<h2 id="orgc8d2e1f">CLH algorithm</h2>
<div class="outline-text-2" id="text-orgc8d2e1f">
<p>
Craig, Landin, and Hagersten，这三个人发明的，所以叫CLH。它是通过链表实现的自旋锁，
每个线程被包装成一个Node结点，加入到链表中，然后不断查询前继结点的状态，如果前继结点释放了，则查询停止，从而结束等待。
</p>
<p>
这种锁在NUMA系统（NUMA参考下面的笔记）下的性能很差，因为它查询的是其他线程结点中的状态，面其他线程也许和当前线程不在同一个CPU模块中，这样就造成远程内存访问。
</p>
</div>
</div>
<div class="outline-2" id="outline-container-org551edee">
<h2 id="org551edee">MCS algorithm</h2>
<div class="outline-text-2" id="text-org551edee">
<p>
John Mellor-Crummey &amp; Michael Scott，这两个发明的，取名字的首字母作为算法名称。目的就是解决CLH在NUMA系统下的问题。
它不再查询前结点的状态，面是将状态保存在自己结点中。这个状态是前结点去更新的。前结点释放锁的时候更新后继结点的状态。
</p>
</div>
</div>
<div class="outline-2" id="outline-container-org1515987">
<h2 id="org1515987">SMP(Symmetric Multi-Processor)</h2>
<div class="outline-text-2" id="text-org1515987">
<p>
Symmetric multi processor architecture, referring to multiple CPU symmetry in the server, the time required for each CPU to access the same memory address. Its main characteristic is shared, include CPU, memory, I/O share. The advantage of the SMP is to ensure memory consistency, the disadvantage is that these shared resources may become a performance bottleneck, with the increase in the number of CPU, each CPU must have access to the same memory resources, likely to cause memory access conflict, may cause the CPU waste of resources. PC machine used to belong to this. 
</p>
<p>
对称多处理器结构：服务器中多个CPU对等，每个CPU访问相同内存地址所需时间相同。
它的主要特征是共享，包含对CPU，内存，I/O的共享。
SMP的优点是保证内存一致性，缺点是这些共享的资源会成为性能瓶颈，当CPU数量增加时，每个CPU都需要访问相同内存资源，容易造成内存访问冲突，浪费CPU资源。
个人计算机曾经就是这种类型的。
</p>
</div>
</div>
<div class="outline-2" id="outline-container-orga5d66e8">
<h2 id="orga5d66e8">NUMA(Non-Uniform Memory Access)</h2>
<div class="outline-text-2" id="text-orga5d66e8">
<p>
Non uniform memory access, CPU is divided into CPU blocks, each CPU module is composed of a plurality of CPU, and have independent local memory, I/O slot, the modules are mutually accessible through Internet access local memory module, the speed will be much higher than the access remote memory (the other nodes in the system speed, memory) this is consistent with non origin memory access NUMA. NUMA advantage is that it can effectively solve the problem extends the original SMP system, due to the shortcomings of remote memory access latency than local memory, so when CPU increases, the system performance can not increase linearly. 
</p>
<p>
非一致内存访问，CPU被分成CPU块，每个CPU模块由多个CPU组成，并且有各自独立的存储，IO槽，模块之间通过（Internet access local memory module ??）访问。
速度远高于访问远程存储（系统中其他结点的存储）。
NUMA的优点是能够有效解决原来SMP系统中的问题。远程存储的访问延迟大于访问本地存储，由于这个原因，当CPU增加时，系统性能并不能线性提升。
</p>
</div>
</div>
</div>
<div class="status" id="postamble">
<p class="author">Author: amo</p>
<p class="validation"><a href="http://validator.w3.org/check?uri=referer">Validate</a></p>
</div>
